home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 029a / pdsrt321.zip / MERGE.C < prev    next >
C/C++ Source or Header  |  1991-07-25  |  4KB  |  168 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <alloc.h>
  5. #include <limits.h>
  6.  
  7. #include "queue.h"
  8.  
  9. typedef struct RunStruct {
  10.     unsigned long   Begin;
  11.     unsigned long   Count;
  12.     }               RUN_ENT;
  13.  
  14. static struct RunArray {
  15.     unsigned long   Current;
  16.     unsigned long   Count;
  17.     int             Index;
  18.     char          **Buf;
  19.     }              *RA;
  20.  
  21. static unsigned long BufSize;
  22. static unsigned BufCount;
  23. static char   **OutBuf;
  24. static unsigned O_Index;
  25. static unsigned Low;
  26.  
  27. void            FillRunBuffer(int x);
  28. void            WriteOutputBuffer(void);
  29. void            PutKeys(void);
  30.  
  31.  void
  32. Merge (void) {
  33.     extern FILE    *fint, *fout;
  34.     extern QUE_DEF  Runs;
  35.     extern int      RecLen;
  36.     extern int        KeySwt;
  37.     extern int      comp(const void *a, const void *b);
  38.     extern char   **SortArray;
  39.     extern unsigned S_ArraySize;
  40.     extern char     IntName[65];
  41.  
  42.     unsigned        i, j;
  43.     QUE_ENTRY      *t;
  44.     RUN_ENT        *p;
  45.     unsigned long   MemLeft;
  46.  
  47.     for (i = 0; i < S_ArraySize; ++i) free(SortArray[i]);
  48.     free(SortArray);
  49.     MemLeft = (S_ArraySize * sizeof(char far *)) + (S_ArraySize * (RecLen + 2));
  50.  
  51.     if ((fint = freopen(IntName, "r", fint)) == NULL) {
  52.         fprintf(stderr, "%s\n", IntName);
  53.         fprintf(stderr, "Major error! %d", errno);
  54.         perror("");
  55.         exit(11);
  56.         }
  57.  
  58.     if ((RA = malloc(Runs.Count * sizeof(struct RunArray))) == NULL) {
  59.         fprintf(stderr, "Major Error. Insufficient memory for run array.\n");
  60.         exit(12);
  61.         }
  62.     MemLeft -= (Runs.Count * sizeof(struct RunArray));
  63.  
  64.     BufSize = MemLeft / (Runs.Count + 1);
  65.     if (BufSize > UINT_MAX) BufSize = UINT_MAX;
  66.     BufCount = (int) (BufSize / (RecLen + 2 + sizeof(char *) + 10));
  67.     BufSize = BufCount * (RecLen + 2);
  68.  
  69.     for (i = 0, t = Runs.Head; t != NULL; ++i, t = t->Next) {
  70.         p = t->Body;
  71.         RA[i].Current = p->Begin;
  72.         RA[i].Count = p->Count;
  73.         RA[i].Index = 0;
  74.         if ((RA[i].Buf = malloc(BufCount * sizeof(char *))) == NULL) {
  75.             fprintf(stderr, "Major Error. Insufficient memory for run item\n");
  76.             exit(12);
  77.             }
  78.         MemLeft -= BufCount * sizeof(char *);
  79.         for (j = 0; j < BufCount; ++j) {
  80.             if ((RA[i].Buf[j] = malloc(RecLen + 2)) == NULL) {
  81.                 fprintf(stderr, "Major Error. Insufficient memory for run item buffer.\n");
  82.                 exit(12);
  83.                 }
  84.             MemLeft -= RecLen + 2;
  85.             }
  86.         }
  87.  
  88.     if ((OutBuf = malloc(BufCount * sizeof(char *))) == NULL) {
  89.         fprintf(stderr, "Insufficient memory: 3\n");
  90.         exit(12);
  91.         }
  92.     MemLeft -= BufCount * sizeof(char *);
  93.     for (j = 0; j < BufCount; ++j) {
  94.         if ((OutBuf[j] = malloc(RecLen + 2)) == NULL) {
  95.             fprintf(stderr, "Insufficient memory: 4\n");
  96.             exit(12);
  97.             }
  98.         MemLeft -= RecLen + 2;
  99.         }
  100.     O_Index = 0;
  101.  
  102.     for (i = 0; i < Runs.Count; ++i) FillRunBuffer(i);
  103.  
  104.     Low = 0;
  105.  
  106.     while (1) {
  107.         for (Low = 0, i = 1; i < Runs.Count; ++i) {
  108.             if (comp(&RA[i].Buf[RA[i].Index], &RA[Low].Buf[RA[Low].Index]) < 0)
  109.                 Low = i;
  110.             }
  111.         if (RA[Low].Buf[RA[Low].Index] == NULL) break;
  112.         strcpy(OutBuf[O_Index++], RA[Low].Buf[RA[Low].Index++]);
  113.         if (RA[Low].Index >= BufCount) FillRunBuffer(Low);
  114.         if (O_Index >= BufCount) WriteOutputBuffer();
  115.         }
  116.  
  117.     if (O_Index > 0) WriteOutputBuffer();
  118.     fclose(fint);
  119.     fclose(fout);
  120.     for (j=0; j < BufCount; j++) free(OutBuf[j]);
  121.     free(OutBuf);
  122.     for (i=0; i < Runs.Count; i++) {
  123.         for (j=0; j < BufCount; j++) free(RA[i].Buf[j]);
  124.         free(RA[i].Buf);
  125.         }
  126.     free(RA);
  127.     if (KeySwt)
  128.         PutKeys();
  129.     }
  130.  
  131.  
  132.  
  133.  void
  134. FillRunBuffer (int x) {
  135.     extern FILE *fint, *fout;
  136.     extern int RecLen;
  137.  
  138.     unsigned        i;
  139.  
  140.     fseek(fint, RA[x].Current, SEEK_SET);
  141.     for (i = 0; (i < BufCount) && (i < RA[x].Count); ++i) {
  142.         fgets(RA[x].Buf[i], RecLen + 1, fint);
  143.         }
  144.     RA[x].Count -= i;
  145.     for (; i < BufCount; ++i) RA[x].Buf[i] = NULL;
  146.     RA[x].Current = ftell(fint);
  147.     RA[x].Index = 0;
  148.     }
  149.  
  150.  
  151.  void
  152. WriteOutputBuffer (void) {
  153.     extern FILE       *fout;
  154.     extern int      errno;
  155.     extern long     OutCount;
  156.     unsigned        i;
  157.  
  158.     for (i = 0; i < O_Index; ++i) {
  159.         fputs(OutBuf[i], fout);
  160.         if (errno) {
  161.             perror("I/O error on output file");
  162.             exit(8);
  163.             }
  164.         OutCount++;
  165.         }
  166.     O_Index = 0;
  167.     }
  168.